package com.le.high.class1;

import org.junit.Test;

import java.util.HashMap;
import java.util.Map;

/**
 * 给出n个数字 a_1,...,a_n，问最多有多少不重叠的非空区间，使得每个区间内数字的 xor都等于0。
 */
public class Problem02_MostEOR {

    public static int mostEOR(int[] arr) {
        int res = 0;
        int xor = 0; // 异或和
        int[] dp = new int[arr.length]; // 0...i 范围上的最优化分
        // key: 当前位置的异或和
        // value: 最晚出现当前key的位置
        Map<Integer, Integer> map = new HashMap<>();
        map.put(0, -1);
        for (int i = 0; i < arr.length; i++) {
            xor ^= arr[i];
            if (map.containsKey(xor)) {
                // 当前位置的异或和 前边存在，则必存在一个最优划分
                Integer val = map.get(xor);
                dp[i] = val == -1 ? 1 : (dp[val] + 1);
            }
            if (i > 0) {
                dp[i] = Math.max(dp[i - 1], dp[i]);
            }
            map.put(xor, i);
            res = Math.max(res, dp[i]);
        }
        return res;
    }

    @Test
    public void test() {
        int[] arr = {1, 2, 3, 0, 4, 5, 5};
        System.out.println(mostEOR(arr));


    }
}
